Logic devices such as FPGAs and ASICs are used to implement large systems that may include million of gates and megabits of embedded memory. The complexity of large systems often requires the use of EDA tools to create and optimize a design for the system onto physical target devices. Among the procedures performed by EDA tools in a computer aided design (CAD) flow are synthesis, placement, and routing. Even with the assistance of EDA tools, the routing phase often takes hours and sometimes days to complete for large designs.
In the past, new processors in computer systems increased clock speeds and reduced the number of cycles required per instruction. This allowed the routing run times for EDA tools to be maintained relatively constant over the years despite the increase in the sizes of the target devices. However, new generations of processors being released today are not using clocks that are significantly faster than previous models. Instead, the new generation processors include more than one processor core inside to allow computers to simultaneously run several “threads” of execution in parallel.
Although a limited number of parallel routing algorithms exist to take advantage of these new generation processors, these parallel routing algorithms typically require significant overhead for broadcasting large amounts of data between threads to support synchronization of data. In addition, prior parallel ASIC global routing and parallel FPGA routing algorithms are not deterministic in that they do not reproduce identical routing results despite being run with exactly the same inputs. This is very problematic for testing.